MPL vi permette di esprimere, brevemente, una moltitudine di vettori, dati, e vincoli, con intuitivi e flessibili formati d'espressione. Nella Sessione 2, siete stati introdotti a variabili semplici, alla funzione obiettivo e a semplici vincoli. In questa sessione, introdurremo diversi e nuovi elementi di modello che sono necessari per la costruzione di modelli con problematiche più ampie.
Il modello che avete usato nella Sessione 2 era di piccole dimensioni, coinvolgeva solo due variabili. In realtà, i modelli hanno centinaia e migliaia di variabili e vincoli, e, a volte, estesi a milioni di variabili. MPL permette all'utente di risolvere un modello usandoIndici, Vettori di Dati, Vettori di Variabili e Vincoli di Vettori per definire il problema in una strada concisa e semplice da leggere.
Gli Indici definiscono il dominio del modello, incapsulano le dimensioni del problema,e rendono più semplice e rapido sistemare il formato di quest'ultimo; una volta che avrete definito gli indici del modello, potrete usarli per definire dati, variabili e vettori di vincolo.
Il regno delle variabili sottoscritte e dei vincoli si trova là dove, un linguaggio di modello, come MPL, può permettere una drammatica produttività, poichè fa sì che chi sviluppa il modello, lo formuli in maniera concisa e semplice da leggere , usando indici e vettori. Esempi di indici includono:
I Vettori sono, praticamente, aggregazioni di elementi nel modello che hanno in comune caratteristiche e scopi. Una volta che avrete definito gli indici in un modello, li potrete usare per definire vettori che contengano i dati, le variabili e i vincoli per il modello stesso. Questo vi permette di lavorare in modo più concentrato, così che non dobbiate battere a macchina ogni elemento ogni volta che ne avete bisogno.
I Vettori di Dati sono usati quando i coefficienti o le statistiche vengono forniti, dal problema, in liste o tabelle di dati numerici. Nel momento in cui viene definito un indice, esiste un valore, per ogni valore dell'indice; i vettori dei dati vi permettono di raggruppare raccolte di dati nel modello. Questi dati possono sia essere specificati come liste o numeri nel file del modello, o essere recuperati in un file esterno, che sarà affrontato nella prossima sessione. Esempi di vettori di dati, in un modello di produzione d' indice 'prodotto' includono:
Vettori di Variabili possono essere definiti in modo simile ai i vettori di dati, per formare una collezione di variabili definite su un certo indice. Esempi di vettori di variabile includono:
I Vettori di Vincoli sono definiti su Indici, che MPL sviluppa in una raccolta di semplici vincoli quando genera il modello. Un vincolo di vettore può essere definito in questo modo, su un numero di Indici, come periodi e prodotti. Esempi di vettori di vincolo includono:
Le Costanti di Dati sono usate, nel modello, per permettere una migliore leggibilità, e rendere la manutenzione del modello più facile . Viene attribuito loro un valore specifico, ma non definito su un indice specifico.
Una delle operazioni eseguite solitamente sui vettori è la sommatoria o l'aggiunta di valori per ogni elemento del vettore. Questo viene eseguito in MPL usando la parola- chiave SUM che circonda l'espressione del vettore al fine di essere sommati insieme. L'espressione è prefissata in una lista di indici, dai quali dipende la somma. L'espressione della somma contiene un singolo vettore di variabile per termine, possibilmente moltiplicata da uno o più vettori di Dati.
SUM(product: Price * Sales);
SUM(product, month: ProdCost * Produce);
State ora per creare la formulazione di un modello per vedere come indici e vettori sono usati in MPL. Abbiamo formulato un piccolo modello di prodotto-misto per una panetteria che contiene due prodotti e tre vincoli. In questo esempio, creerete un modello simile, ma questo incuderà tre prodotti, che saranno chiamati A1, A2, e A3. Per questi tre prodotti creerete un indice, e poi creerete un vettore di variabile che rappresenti quanto di ognuno di questi prodotti debba essere prodotto.
Date le definizioni di questi nuovi termini, indici e vettori, stiamo per applicarli ad un modello campione. Il modello di prodotti-misto si occupa di come distribuire la capacità della produzione tra prodotti, e determinare il livello della produzione, fornendo la richiesta.
Il prezzo di vendita per ogni prodotto è fisso: $120.00 per A1, $100.00, perA2, e $115.00 per A3. Esiste, inoltre, un limite nella richiesta massima per ogni prodotto: 4300 per A1, 4500 per A2, e 5400 per A3.
Il tasso di produzione viene misurato da quanti articoli di ogni prodotto vengono prodotti ogni giorno. In questo problema, avete un totale di 22 giorni di produzione disponibili. Il costo di produzione è diverso per ogni prodotto. Il tasso di produzione e il costo di produzione per ogni prodotto è mostrato nella tabella sottostante:
| Produzione | A1 | A2 | A3 |
|---|---|---|---|
| Costo di Produzione | $73.30 | $52.90 | $65.40 |
| Tasso di Produzione | 500 | 450 | 550 |
Il prossimo passo sarà quello di prendere il problema descritto nella sessione precedente e formularlo in un modello di MPL. Per vedere una descrizione del modello Planning3 che deve essere creato, viene mostrata, qui sotto, una completa lista della formulazione del modello.
TITLE
Production_Planning3;
INDEX
product := (A1, A2, A3);
DATA
Price[product] := (120.00, 100.00, 115.00);
Demand[product] := (4300, 4500, 5400);
ProdCost[product] := (73.30, 52.90, 65.40);
ProdRate[product] := (500, 450, 550);
ProdDaysAvail := 22;
VARIABLES
Produce[product] -> Prod;
MACROS
TotalRevenue := SUM(product: Price * Produce);
TotalCost := SUM(product: ProdCost * Produce);
MODEL
MAX Profit = TotalRevenue - TotalCost;
SUBJECT TO
ProdCapacity -> PCap:
SUM(product: Produce / ProdRate) <= ProdDaysAvail;
BOUNDS
Produce <= Demand;
END
Affronterete, ora, un semplice modello, passo dopo passo, di modo che possiate capire come regolare la formulazione del modello.
Eseguire l'applicazione MPL
Scegliere New (Nuovo) dal menu File (Archivio) per creare un nuovo file di modello vuoto.
Scegliere Save As (Salva come) dal menu File (Archivio) e salvare il file di modello con il nome di Planning3.mpl.
Il titolo è opzionale, ma è conveniente dare un nome al modello. Il titolo sarà usato nel file della soluzione per identificare il modello. Dovreste, ora, avere una finestra editor vuota dove potete introdurre la vostra formulazione MPL. Inserire il titolo per il modello Planning3, comporre il seguente testo nell'editor del modello:
TITLE
Production_Planning3;
La prima sezione in un modello MPL è solitamente la sezione INDEX (Indice) dove definite gli indici per il modello.In questo esempio, avete tre prodotti, A1, A2, e A3 per i quali state creando un indice chiamato prodotto. Nell'editor del modello, direttamente sotto al titolo, aggiungere una sezione INDEX (Indice) con una definizione per l'indice del prodotto come segue:
INDEX
product := (A1, A2, A3);
La prossima sezione in MPL è solitamente la sezione DATA (Dati) dove si definiscono i Vettori dei Dati e le Costanti dei Datiper il modello. Il primo vettore di dati che introdurrete, contiene i prezzi per ogni prodotto, che sono stati forniti nella descrizione del problema.
Nell'editor del modello, direttamente sotto la descrizione dell'indice, aggiungere una sezione DATA (Dati) con la definizione per il vettore di dati Price (Prezzo) seguito dall'indice [product] dentro alle parentesi:
DATA
Price[product] := (120.00, 100.00, 115.00);
Dopo la dichiarazione, introducete un simbolo di assegnazione ':=' e poi una lista di numeri contenenti i prezzi di ogni prodotto. Cerchiare la lista con parentesi e separare ogni numero sia con spazi che con virgole o con entrambi.Dovrebbe esserci un punto e virgola dopo ogni definizione di vettore di dati per separarlo dalle altre definizioni nel modello.
La descrizione del problema, inoltre, elenca dati per la richiesta, costo di produzione e tasso di produzione. C'è una certa domanda per ogni prodotto che si può produrre giornalmente. Per introdurre questi dati inMPL, aggiungere le seguenti definizioni alla sezione DATI direttamente sotto il vettore di dati Prezzo:
Demand[product] := (4300, 4500, 5400);
ProdCost[product] := (73.30, 52.90, 65.40);
ProdRate[product] := (500, 450, 550);
La descrizione del problema, in più, elenca quanti giorni di produzione sono disponibili. aggiungere la seguente definizione di costante di dati per i giorni di produzione disponibili direttamente sotto il vettore di dati ProdRate (Tasso di Produzione):
ProdDaysAvail := 22;
Solitamente, la prossima sezione dovrebbe essere la sezione delle VARIABILI dove si definiscono le variabili per i modelli. Nella descrizione del problema, vi è stato chiesto di usare il modello per determinare quanto si produce di ogni prodotto.Per fare questo avete bisogno di definire una variabile di vettore chiamata Produce (Produrre) sul prodotto index (indice). Nell'editor del modello, direttamente sotto le definizioni di dati aggiungere la sezione VARIABLES con una definizione per la variabile di vettore Produce come segue:
VARIABLES
Produce[product] -> Prod;
Il nome che appare dopo il simbolo '->' (read becomes) è un' abbreviazione opzionale per il,nome del vettore usato per compensare le limitazioni di misura del nome della maggior parte dei solver LP. Questo vi permette di usare lunghi e descrittivi nomi per le variabili nel vostro modello.
Nella descrizione del problema, vi è stato chiesto di massimizzare il profitto per l'azienda, che è rappresentato come Total revenue - Total cost (Reddito Totale- Costo Totale). Il reddito totale è calcolato moltiplicando il prezzo per ogni prodotto per quanto di quel prodotto è stato prodotto. Allo stesso modo, il costo totale è calcolato moltiplicando il costo di produzione per ogni prodotto per la quantità prodotta per quel prodotto. Queste sommatorie saranno usate per definire la funzione obiettivo per il modello.
Quando s'introducono delle sommatorie per la funzione obiettivo è utile definirle separatamente come macros, per rendere il modello più semplice da leggere. Usando macro potete poi, nel modello, far riferimento a queste sommatorie usando macro nomi. Nell'editor del modello, direttamente sotto la definizione della variabile, introdurre le seguenti definizioni di macro nella sezione MACROS.
MACROS
TotalRevenue := SUM(product: Price * Produce);
TotalCost := SUM(product: ProdCost * Produce);
La parte del modello in MPL si trova dove viene definita l' attuale funzione obiettivo e i limiti per il modelllo. Userete le macro, definite sopra, per creare la funzione obiettivo con riferimento ai nomi della macro dove dovete usare la sommatoria. Dato che state massimizzando il profitto in questo modello, il nome di questa funzione obiettivo sarà Profit (Profitto). Nell'editor del modello, introdurre la parola MODEL (Modello) per annotare l'inizio della parte del modello, seguito dalla definizione per la funzione obiettivo:
MODEL
MAX Profit = TotalRevenue - TotalCost;
La formula per la funzione obiettivo è abbastanza semplice, dato che stiamo usando macro per contenere le attuali sommatorie. Questo risulta nella funzione obiettivo determinando come massimizzare il profitto elaborando le differenze tra redditi e costo totale.
Di seguito alla funzione obiettivo avete bisogno di definire i vincoli per il modello nellla sezione SUBJECT TO (Soggetto a ). Nella descrizione del problema, vi è stato dato il tasso di produzione definito come molti articoli di ogni prodotto che potete produrre ogni giorno. Così come quanto produzioni al giorno sono disponibili. Dato che questo definisce quanti articoli potete produrre, avete bisogno di creare un vincolo di capacità di produzione chiamato ProdCapacity, per ogni prodotto.
Nell'editor del modello, aggiungere l'intestazione SUBJECT TO, seguito hdalla definizione del vincolo:
SUBJECT TO
ProdCapacity -> PCap:
SUM(product: Produce / ProdRate) <= ProdDaysAvail;
Nella sommatoria, dividete il numero degli articoli prodotti dal tasso di produzione per avere il numero totale di giorni utilizzati per produrre ogni prodotto. I totali giorni di produzione utilizzati devono essere meno dei giorni disponibili per la produzione.
La sezione LIMITI viene utilizzata per definire i limiti superiori e inferiori nelle variabili nel modello. I limiti sono simili ai vincoli ma sono circoscritti solo ad una variabile per limite. Nella descrizione del problema, abbiamo specificato che il numero totale degli articoli prodotti deve essere meno della richiesta. Quindi, introdurre il seguente limite superiore nella variabile Produce nella sezione BOUNDS (LIMITI).
BOUNDS
Produce <= Demand;
END
Per favore, si noti che, nella maggior parte dei modelli di programmazione lineare, tutte le variabili hanno un limite implicito minore di zero. Questi limiti minori sono automaticamente trattati da MPL e non devono essere specificati a meno che siano diversi da zero.
Alla fine del modello introdurre la parola chiave END per informare che il modello è terminato. Dopo aver finito d'introdurre il modello, dovreste salvarlo scegliendo Save (Salvare) dal menu File (Archivio).
Il prossimo passo è risolvere il modello Planning3. risolvere il modello coinvolge diversi compiti fatti automaticamente da MPL incluso il controllo della sintassi, analisi del modello nella memoria, trasperire il modello al solver, risolvere il modello e poi ricuperare la soluzione dal solver e creare il file di soluzione.Tutti questi compiti sono fatti chiaramente dall'utente quando sceglie il comando della soluzione dai menu. Per risolvere il modello seguire i seguenti passi:
Scegliere Solve CPLEX dal menu Run o premere il tasto Run Solve nella Toolbar.
Mentre si risolve il modello la the Status Window sembra fornirvi l'informazione circa il progresso della soluzione.
La Status Window per il modello Planning3
Se tutto procede bene MPL visualizzerà il messaggio "Optimal Solution Found". Se c'è una finestra con un messaggio d'errore con un errore di sintassi, per favore, si controlli la formulazione che avete introdotto con il modello descritto prima in questa sessione.
Dopo aver risolto il modello MPL automaticamente crea un file standard di soluzione contenente vari elementi della soluzione del modello. Questo include, tra le altre cose, il valore ottimale della funzione obiettivo, l'attività e i costi ridotti per le variabili, e i prezzi di slack e ombra per i vincoli. Questo file di soluzione è creato con lo stesso nome del file di modello, ma con l'aggiunta di '.sol'. Nel nostro caso il file di soluzione è chiamato 'Planning3.sol'.
Dopo che avete risolto il modello, potete visualizzare il file di soluzione in una finistra di visuale premendo il tasto View sul fondo della Status Window. Questo visualizzerà la finestra mostrata qui sotto.
View Window con il file di soluzione Planning3.sol
View Window immagazzina il file di soluzione nella memoria, permettendovi di curiosare attraverso le soluzioni usando le scroll bars. Un elenco completo di file disoluzione per il modello Planning3 è mostrata qui sotto:
MPL Modeling System - Copyright (c) 1988-1999, Maximal Software, Inc.
--------------------------------------------------------------------------------
MODEL STATISTICS
Problem name: Producton_Planning3
Filename: Planning3.mpl1
Date: April 18, 1998
Time: 09:59
Parsing time: 0.57 sec
Solver: CPLEX
Objective value: 544566.636364
Iterations: 3
Solution time: 0.12 sec
Constraints: 1
Variables: 3
Nonzeros: 3
Density: 100 %
SOLUTION RESULT
Optimal solution found
MAX Profit = 544566.6364
MACROS
Macro Name Values
-----------------------------------------------
TotalRevenue 1298181.8182
TotalCost 753615.1818
-----------------------------------------------
DECISION VARIABLES
VARIABLE Produce[product] :
product Activity Reduced Cost
---------------------------------------------
A1 4300.0000 4.3100
A2 1611.8182 0.0000
A3 5400.0000 11.0636
---------------------------------------------
CONSTRAINTS
PLAIN CONSTRAINTS
Constraint Name Slack Shadow Price
------------------------------------------------------
ProdCapacity 0.0000 -21195.0000
------------------------------------------------------
END
La prima parte del file di soluzione contiene diverse statistiche per il modello come il nome del file, la data e il tempo in cui il modello è stato risolto, quale solver è stato usato, il valore della funzione obiettivo e la grandezza del modello.
La parte seguente del file di soluzione contiene i risultati della soluzione. Qui potete vedere se la soluzione che è stata trovata era ottimale, se era illimitata o impossibile.Esso inoltre vi mostra il nome e il valore ottimale per la funzione obiettivo.
Nella sezione MACROS del file di soluzione avete una lista di tutti i macros definiti nel modello insieme ai loro valori di soluzione. Per esempio, nel nostro modello Planning3, il reddito totale è $1.298 milioni e il costo totale è $754,000. Questo corrisponde ad un profitto di $545,000, che è il valore della funzione obiettivo.
Nella sezione della VARIABILE DI DECISIONE avete una lista di tutte le variabili nel modello, entrambe le variabili di vettore e le variabili semplici. Nel nostro caso, abbiamo una singola variabile di vettore Produrre definita sull' indice prodotto. Vedrete che per il prodotto A1 e A3 la soluzione suggerisce che si produca 4300 e 5400 unità rispettivamente.Questa è la stessa quantità della richiesta per quei prodotti. D'altra parte il prodotto A2 suggerisce di produrre 1612 unità che è meno della richiesta. Chiaramente non abbiamo la capacità di produrne abbastanza per esaudire la richiesta per tutti i prodotti e il modello ha scelto i prodotti A1 e A3per eseguire la richiesta.
A proposito, dovreste aver notato che il valore di A2 nell'output della soluzione è realmente 1611.8182 unità invece di 612. Questo risulta dal fatto che tutte le variabili nei modelli di Programmazione Lineare sono per difetto continui. In questo modello non ha molta importanza e possiamo solo arrotondarli fino al numero più vicino 1612, ma se viene fatto, potreste aver limitato la variabilr per prendere solo i valori interi specificandola come variabile di numero intero nel modello. Per favore vedere il Manuale dell'utente di MPL per maggior dettagli su come formulare modelli in MPL con variabili di numero intero.
Nella sezione dei VINCOLI il file di soluzione elenca tutti vincoli per il modello, ancora entrambi vincoli semplici e di vettore. Nel nostro modello, noi avevamo un vincolo singolo e semplice chiamatoProdCapacity. Dato che lo slack per il vincolo è 0.0 questo significa che stiamo producendo a piena capacità. Il prezzo d'ombra ci dice quello che il costo marginale sarebbe se avessimo bisogno di ridurre il limite del vincolo a una unità. Dato che il vincolo della capacità di produzione ha giorni di produzione come unità, riducendo i giorni disponibili in un giorno, il profitto diminuirebbe a $21,195.